Databases have been used for various purposes, and relational databases (RDBs), which can eliminate logical inconsistencies, have been mainly used for medium-scale or large-scale systems. For example, RDBs are used for airplane seat reservation systems. In this case, by specifying a key item, it is possible to quickly search for targets (in most cases, one target) or it is possible to confirm, cancel or change a reservation. Since the number of seats on each flight is at most several hundred, the number of seats available on a specific flight can also be determined.
It is known that such RDBs are not suitable for handling tree-type data but are suitable for table-format data (e.g., refer to Non-Patent Document 1).
Additionally, there are some applications that can be more appropriately represented by tree-type formats than table formats. In recent years, particularly, an XML employing a tree data structure has been widely used as a data standard for intranet or Internet applications (e.g., refer to Non-Patent Document 2 for details of an XML).
In general, however, the handling of tree data structures, for example, searching for tree data, is very inefficient. A first reason for the inefficiency is that data are distributed at separate nodes and it is thus very difficult to immediately identify the locations of the data. In RDBs, for example, data “age” is stored only at an item labeled “age” in a certain table. In a tree data structure, however, since nodes at which data “age” are stored are distributed at various locations, data of interest cannot generally be searched for unless the entire tree data structure is checked.
A second reason for the inefficiency is that it takes a long time to represent search results. Representing a group of nodes found by searching often requires representing nodes corresponding to respective descendant nodes of the nodes as well. However, unlike an RDBMS, the tree data structures do not have a standard format; therefore, it takes a long time to represent the descendant nodes.
Accordingly, in order to take advantage of RDBs, which are mainly used as databases, a method for converting tree-type data into an RDB during conversion of the tree-type data into a database has been proposed (e.g., refer to Patent Document 1). In RDBs, data are separately contained in a table (tabular form) for storage. Thus, in order to convert actual tree data into an RDB, it is necessary to insert tree-type data into a table. However, in order to handle various tree data structures, the system design must be such that data from the various data structures are individually inserted into a table for the respective data structures. Thus, the system construction based on an RDB is a very time-consuming process.
In contrast, a method for converting tree-type data, particularly, XML data, into a database while keeping its original format has also been proposed. In the case of a tree data structure, since descendant nodes can be connected to one node and various types of representation are possible, the time and effort required for the system design can be significantly reduced. Thus, there is an increasing demand for processing tree-type data by mainly using a technology that allows handling of a tree data structure adopting an XML or the like.
One example approach for a method for converting XML data into a database while maintaining its original format is such that a copy of data written in a tree data structure is retrieved and, for example, for an item “age”, index data for searching “age” is separately stored (e.g., refer to Patent Document 2). This makes it possible to fully utilize the advantage of XML data, i.e., the capability of adding attributes to the data itself, and also makes it possible to store a relational structure of individual items represented by tags as it is.    Patent Document 1: Japanese Unexamined Patent Application Publication No. 2003-248615    Patent Document 2: Japanese Unexamined Patent Application Publication No. 2001-195406    Non-Patent Document 1: SEC Co., Ltd. “Karearea White Paper”, [online], [searched on Feb. 19, 2004], Internet <URL: http://www.sec.co.jp/products/karearea/>    Non-Patent Document 2: W3C, “Extensible Markup Language (XML) 1.0 (Third Edition)”, [online], Feb. 4, 2004, [searched on Feb. 19, 2004], Internet <URL: http://www.w3.org/TR/2004/REC-xml-20040204/>